package com.example.summary.lianxi;

import com.alibaba.fastjson.JSONObject;

import java.util.HashMap;

/**
 * Created by wzn on 2019/6/12.
 */
public class ZouQiPan {
    public static int[][] init = {{0, 3, 5, 9}, {2, 1, 3, 4}, {5, 2, 6, 7}, {6, 8, 4, 3}};

    static int[][] lujin = new int[init[0].length][init.length];

    static int length = Integer.MAX_VALUE;

    public static void main(String[] args) {
//        min(0, 0, init, lujin, 0);
//        System.out.println(JSONObject.toJSONString(min(init)));
        minDongTaiGuiHua(0, 0, init, lujin);
        System.out.println(JSONObject.toJSONString(lujin));
    }


    public static void minHuiShu(int x, int y, int[][] init, int temp) {
        temp = temp + init[x][y];

        if (x == init[0].length - 1 && y == init.length - 1) {
            if (temp < length) {
                length = temp;
                return;
            }
        }

        if (x < init[0].length - 1) {
            minHuiShu(x + 1, y, init, temp);
        }

        if (y < init.length - 1) {
            minHuiShu(x, y + 1, init, temp);
        }

    }

    public static int[][] min(int[][] init) {
        int[][] lujin = new int[init[0].length][init.length];

        int sum = 0;

        /**
         * 初始化第一行
         */
        for (int i = 0; i < init.length; i++) {
            sum += init[0][i];
            lujin[0][i] = sum;
        }

        sum = 0;

        /**
         * 初始化第一列
         */
        for (int i = 0; i < init.length; i++) {
            sum += init[i][0];
            lujin[i][0] = sum;
        }

        for (int i = 1; i < init[0].length; i++) {
            for (int j = 1; j < init.length; j++) {
                lujin[i][j] = init[i][j] + Math.min(lujin[i][j - 1], lujin[i - 1][j]);
            }
        }

        return lujin;
    }

    public static void minDongTaiGuiHua(int x, int y, int[][] init, int[][] lujin) {

        if (x >= init[0].length - 1 && y >= init.length - 1) {
            return;
        }

        if (x >= init[0].length - 1 && y < init.length - 1) {
            y = y + 1;
        }

        if (y >= init.length - 1 && x < init[0].length - 1) {
            x = x + 1;
        }

        if (x < init[0].length - 1 && y < init.length - 1) {
            if (init[x][y + 1] <= init[x + 1][y]) {
                y = y + 1;
            } else {
                x = x + 1;
            }
        }

        lujin[x][y] = init[x][y];

        minDongTaiGuiHua(x, y, init, lujin);
    }

}
